На фундаментальном уровне связанный список — это связанный список рекурсивная структура данных, определяемая либо отсутствием, либо составом. Список либо пустой (обозначается как []), либо состоит из головы содержащей одно значение и хвоста который сам по себе является полным списком.

1. Рекурсивное определение

Определяя хвост как «сам по себе список», мы позволяем бесконечную вложенность. Это демонстрируется конструкцией [ 1 | [ 2 | [ 3 | [ ] ] ] ], где каждый оператор-вертикальная черта (|) разделяет непосредственное значение от оставшейся структуры.

2. Примитивные структуры и абстракции

Примитивные списки в виртуальной машине Эрланга (BEAM) — это простые структуры. Поведения, такие как List.flatten/1 являются абстракциями предоставляемыми модулем списков Эликсира. Исходная структура данных не «знает», как сама себя расплести; модуль предоставляет логику для обхода вложенных голов и хвостов.

3. Аналогия с русскими матрёшками

Представьте связанный список как комплект русских матрёшек. Самая внешняя кукла — это головы. Когда вы открываете её, вы видите только одну вещь: другую куклу (тот хвоста). Вы достигаете состояния Пустого только тогда, когда вы открываете последнюю, самую маленькую куклу и ничего внутри не находите.